home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / BARNET / COMPILER / SATHER / !Sather / Library / Containrs / sa / fgap_list < prev    next >
Text File  |  1996-06-01  |  6KB  |  183 lines
  1. ---------------------------> Sather 1.1 source file <--------------------------
  2. -- gap_list.sa<2>: Gap lists
  3. -- Author: Benedict A. Gomes <gomes@samosa.ICSI.Berkeley.EDU>
  4. -- Translated from the original by S. Omohundro
  5. -- Copyright (C) 1995, International Computer Science Institute
  6. -- $Id: fgap_list.sa,v 1.4 1996/06/01 21:36:19 gomes Exp $
  7. --
  8. -- COPYRIGHT NOTICE: This code is provided WITHOUT ANY WARRANTY
  9. -- and is subject to the terms of the SATHER LIBRARY GENERAL PUBLIC
  10. -- LICENSE contained in the file: Sather/Doc/License of the
  11. -- Sather distribution. The license is also available from ICSI,
  12. -- 1947 Center St., Suite 600, Berkeley CA 94704, USA.
  13. -------------------------------------------------------------------
  14.  
  15. --=============================================================================
  16. class FGAP_LIST{T} < $STR is
  17.    -- An array replacement for linked lists.
  18.    -- The class `GAP_LIST{T}' is an array based list structure like `LIST{T}'
  19.    -- but it supports insertions and deletions from the middle of the list
  20.    -- as well as the end.  This structure consists of an extensible array
  21.    -- with a "gap" region in the middle. When an insertion or deletion is
  22.    -- required, the gap is first moved to the proper location by moving
  23.    -- elements around.  Element access is by index and skips over the gap
  24.    -- wherever it may lie. As long as most insertions and deletions are
  25.    -- fairly close in location to the preceding one, the movement of
  26.    -- elements accross the gap will not be extensive. Algorithms which are
  27.    -- based on doubly linked lists often have a single pointer which moves
  28.    -- up and down the list inserting and deleting elements as it moves. Such
  29.    -- algorithms will also operate efficiently with gap lists.  Sometimes
  30.    -- this structure is refered to as a "double stack" since it may be
  31.    -- viewed as two stack which approach one another. It has found wide use
  32.    -- in text editors (such as GNU Emacs) and turns out to be much more
  33.    -- efficient in practice than more obvious structures such as a linked
  34.    -- list of strings for each line.
  35.    private include COMPARE{T};
  36.    private include AREF{T};
  37.  
  38.    private attr gap_start,gap_size: INT;    
  39.    -- Start of gap and size of gap.
  40.  
  41.    --              ------ Initialization/Duplication ------
  42.    create: SAME is
  43.       -- A new `GAP_LIST' with default `size=5'.
  44.       res ::= new(5); 
  45.       res.gap_size := 5;
  46.       return res;
  47.    end; -- create
  48.    
  49.    create(a: $ELT{T}): SAME is
  50.       res ::= #SAME;
  51.       loop res := res.append(a.elt!) end;
  52.       return res;
  53.    end;
  54.       
  55.    create_sized(n: INT): SAME is
  56.       -- A new `GAP_LIST' with `size=n'.
  57.       res ::= new(n); 
  58.       res.gap_size := n;
  59.       return res;
  60.    end; -- create_sized
  61.  
  62.    --              ------ Insertion/Removal --------------- 
  63.    append(e: T): SAME is return insert(size,e) end;
  64.    
  65.    insert(i: INT, e: T): SAME pre 0 <= i and i <= size is
  66.       -- Insert element `e' at location `i' pushing later elements forward.
  67.       -- Elements may be inserted anywhere in the list or at the very end
  68.       -- of the list
  69.       res ::= self;
  70.       if gap_size = 0 then        -- no gap, so double size
  71.      res := new(2 * asize); 
  72.      res.gap_start := asize; 
  73.      res.gap_size := res.asize - res.gap_start; 
  74.      loop res.set!(elt!) end;
  75.      clear;            -- help the garbage collector
  76.       end; -- if
  77.       res.move_gap(i);
  78.       res[i] := e;
  79.       res.gap_start := res.gap_start + 1;
  80.       res.gap_size := res.gap_size - 1;
  81.       return res;
  82.    end; -- insert
  83.    
  84.    delete(i: INT): SAME  pre has_ind(i) is 
  85.       -- Delete the `i'th element.
  86.       move_gap(i); 
  87.       gap_size := gap_size + 1;
  88.       return self;
  89.    end; -- delete
  90.    
  91.    replace(i: INT, e: T) pre has_ind(i) is
  92.       -- Replace the `i'th element by `e'.
  93.       if i < gap_start then [i] := e else [gap_size + i] := e end;
  94.    end; -- replace
  95.  
  96.    clear is
  97.       -- Clear the list.
  98.       i: INT := 0; loop until!(i=asize);
  99.      [i] := elt_nil;
  100.      i := i + 1
  101.       end; -- loop
  102.       gap_start := 0; 
  103.       gap_size := asize;
  104.    end; -- clear
  105.  
  106.    --              ------ Access/Measurement --------------
  107.    get(i: INT): T is
  108.       -- Retrieve the `i'th element.
  109.       if i < gap_start then return [i] else return [gap_size + i] end;
  110.    end; -- get
  111.  
  112.    
  113.    set(i: INT,val: T) is
  114.       -- Set the ith element
  115.       if i < gap_start then [i] := val else [gap_size + i] := val; end;
  116.    end; -- get
  117.  
  118.    size: INT is
  119.       -- The total number of elements.
  120.       return asize - gap_size;
  121.    end; -- size
  122.  
  123.    --              ------ Queries/Comparison --------------
  124.    is_empty: BOOL is
  125.       -- True if `self' is empty.
  126.       return (gap_size = asize);
  127.    end; -- is_empty
  128.  
  129.    has_ind(i: INT): BOOL is return (0 <= i and i < size) end;
  130.    
  131.    equals(e: $ARR{T}): BOOL is
  132.       if e.size /= size then return false end;
  133.       loop if ~elt_eq(e.elt!,elt!) then return false end; end;
  134.       return true;
  135.    end;
  136.       
  137.    --              ------ Cursor --------------------------
  138.    elt!: T is
  139.       i ::= 0; sz ::= size;
  140.       loop until!(i = sz); yield get(i); i := i + 1; end;
  141.    end;
  142.  
  143.    set!(e: T) is
  144.       i ::= 0; sz ::= size;
  145.       loop until!(i = sz); [i] := e; yield; i := i + 1; end;
  146.    end;      
  147.    
  148.    str: STR is
  149.       -- Prints out a string version of the flist of the components 
  150.       -- that are under $STR
  151.       res ::= #FSTR("{");
  152.       loop 
  153.      e ::= elt!;
  154.      typecase e
  155.      when $STR then res := res+",".separate!(e.str); 
  156.      else -- do nothing
  157.      end;
  158.       end;
  159.       res := res+"}";
  160.       return(res.str);
  161.    end;
  162.    
  163.    --              ------ Implementation ------------------
  164.    private move_gap(l: INT) pre l <= size is
  165.       -- Move the gap to start at `l'. Must have `l<=size'.
  166.       if l <= gap_start then
  167.      b: INT := l + gap_size;
  168.      i: INT := gap_start + gap_size - 1; 
  169.      loop until!(i < b);
  170.         [i] := [i - gap_size];
  171.         i := i - 1
  172.      end; -- loop
  173.       else
  174.      i: INT := gap_start; 
  175.      loop until!(i = l);  [i] := [i + gap_size];  i := i + 1 end; -- loop
  176.       end; -- if
  177.       gap_start := l;
  178.    end; -- move_gap
  179.    
  180.    
  181. end;
  182. --~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  183.